import java.util.*;

public class day3 {
    /**
     * DP43 最少的完全平方数
     * https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04?tpId=230&tqId=40431&ru=/exam/oj
     */
    // 空间优化
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // 动态规划 - 完全背包
        // dp[i][j]: 表示用前 i 个平方数组成和 j 所需的最少数量。
        int[] dp = new int[n + 1];
        // 初始化，全为负
        for(int j = 0;j <= n;j++) {
            dp[j] = (int)1e16;
        }
        dp[0] = 0;

        for(int i = 1;i * i <= n;i++) {
            for(int j = i * i;j <= n;j++) {
                dp[j] = Math.min(dp[j],dp[j - i*i] + 1);
            }
        }
        System.out.println(dp[n]);
    }
    // 不进行空间优化
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        // 动态规划 - 完全背包
        // dp[i][j]: 表示用前 i 个平方数组成和 j 所需的最少数量。
        int[][] dp = new int[n + 1][n + 1];
        // 初始化，全为负
        for(int i = 0;i <= n;i++) {
            for(int j = 0;j <= n;j++) {
                dp[i][j] = (int)1e16;
            }
        }
        dp[0][0] = 0;

        for(int i = 1;i * i <= n;i++) {
            for(int j = 0;j <= n;j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= i * i) {
                    dp[i][j] = Math.min(dp[i][j],dp[i][j - i*i] + 1);
                }
            }
        }
        System.out.println(dp[(int)Math.sqrt(n)][n]);
    }





    /**
     * MT7 字符编码
     * https://www.nowcoder.com/practice/c471efdbd33a4a979539a91170c9f1cb?tpId=128&tqId=33774&ru=/exam/oj
     */
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            char[] s = in.next().toCharArray();
            // 先统计出现的次数每个字符
            int[] hash = new int[300];
            for(char ch : s) {
                hash[ch]++;
            }
            // 将所有的频次放入堆中
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            // 默认小根堆
            for(int x : hash) {
                if(x > 0) {
                    heap.offer(x);
                }
            }

            int ret = 0;
            // 每次取最小的两个值，进行组合，之后记录，之后将结果放入堆中，直至堆中没有数据
            while(heap.size() > 1) {
                int t1 = heap.poll();
                int t2 = heap.poll();
                heap.offer(t1 + t2);
                ret += (t1 + t2);
            }
            System.out.println(ret);
        }
    }



    /**
     * 神奇的字母（二）
     * https://ac.nowcoder.com/acm/problem/205832
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        char ret = '0';
        int count = 0;
        int[] hash = new int[26];

        while(in.hasNext()) {
            char[] s = in.next().toCharArray();
            for(char ch : s) {
                int x = ch - 'a';
                if(++hash[x] > count) {
                    ret = ch;
                    count = hash[x];
                }
            }
        }
        System.out.println(ret);
    }
}
